package com.jz.pay3;

import java.util.*;

public class Study {
    /**
     * 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target 的那两个整数，并返回它们的数组下标。
     *
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     *
     * 你可以按任意顺序返回答案。
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSums(int[] nums,int target){
        Map<Integer,Integer> map = new HashMap<>(nums.length);
        int[] data = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(target-nums[i])){
                data[0] = i;
                data[1] = map.get(target-nums[i]);
                break;
            }else{
                map.put(nums[i], i);
            }
        }
        return data;
    }

    private void twoSumsTest(){
        int[] data1 = {1,2,3,4,5,6,7,8,9,10};
        int[] data2 = {5,7,3,2,1,9,4,8,6,10};
        int[] data3 = {5,7,10,2,1,9,4,8,6,3};
        int[] data4 = {5,7,10,8,1,9,4,2,6,3};
        int target = 19;
        int[] result = twoSums(data1,target);
        int[] result2 = twoSums(data2,target);
        int[] result3 = twoSums(data3,target);
        int[] result4 = twoSums(data4,target);
        System.out.println(result[0]+","+result[1]+" ; "+data1[result[0]]+","+data1[result[1]]);
        System.out.println(result2[0]+","+result2[1]+" ; "+data2[result2[0]]+","+data2[result2[1]]);
        System.out.println(result3[0]+","+result3[1]+" ; "+data3[result3[0]]+","+data3[result3[1]]);
        System.out.println(result4[0]+","+result4[1]+" ; "+data4[result4[0]]+","+data4[result4[1]]);
    }

    ////////////////////////////////////////////////////////////////////////////////////////////////////////////
    /**
     * Definition for singly-linked list.
     */
    public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2){
        ListNode[] arry1 = toArray(l1);
        ListNode[] arry2 = toArray(l2);
        if(arry2.length > arry1.length){
            ListNode[] arry3 = arry1;
            arry1 = arry2;
            arry2 = arry3;
        }
        ListNode lastNode = arry1[0];
        int next = 0;
        for (int i = 0; i < arry1.length; i++) {
            int sum = arry1[i].val + (i > arry2.length-1 ? 0:arry2[i].val ) + next;
            next = sum > 9 ? 1 : 0 ;
            arry1[i].val = sum > 9 ? sum-10 : sum;
            if(lastNode != arry1[i]){
                lastNode.next = arry1[i];
                lastNode = arry1[i];
            }
        }
        if(next > 0){
            lastNode.next = new ListNode(1);
        }
        return arry1[0];
    }

    ListNode[] toArray(ListNode listNode){
        LinkedList<ListNode> list = new LinkedList<>();
        do {
            list.add(listNode);
            listNode = listNode.next;
        }while (listNode!=null);
        return list.toArray(new ListNode[]{});
    }

    void addTwoNumbersTest(){
        ListNode l1 = new ListNode(2,new ListNode(4,new ListNode(3)));
        ListNode l2 = new ListNode(5,new ListNode(6,new ListNode(4)));
        ListNode result = addTwoNumbers(l1,l2);
        l1 = new ListNode(2,new ListNode(4,new ListNode(5)));
        l2 = new ListNode(5,new ListNode(6,new ListNode(4)));
        result = addTwoNumbers(l1,l2);
        System.out.println();
    }

    ///////////////////////////////////////////////////////////////////////////////////////////////////////////

    /**
     * 判断9*9的数独是否有效
     * @param board
     */
    public boolean isValidSudoku(char[][] board){
        int k = 3;
        int colLenth = board.length;
        for (int i = 0; i < colLenth; i++) {
            int lineLength = board[i].length;
            for (int j = 0; j < lineLength; j++) {
                if(board[i][j] != '.'){
                    // 横排 遍历
                    for (int h = j+1; h < lineLength; h++) {
                        if (board[i][j] == board[i][h]){
                            return false;
                        }
                        // 遍历九宫格剩下的格子，锁定列后，按照行遍历
                    }
                    // 竖排 遍历
                    for (int h = i+1; h < colLenth; h++) {
                        if (board[i][j] == board[h][j]){
                            return false;
                        }
                    }
                    // 九宫格 遍历
                    int row = i/k*k; // 顶格子
                    int col = j/k*k; // 顶格子
                    for (int l = row; l < row+k; l++) {
                        for (int m = col; m < col+k; m++) {
                            if(l!=i && m!=j){
                                if(board[l][m] == board[i][j]){
                                    return false;
                                }
                            }
                        }
                    }
                }
            }
        }
        return true;
    }

    void isValidSudokuTest(){
        char[][] board1={{'5','3','.','.','7','.','.','.','.'}
                        ,{'6','.','.','1','9','5','.','.','.'}
                        ,{'.','9','8','.','.','.','.','6','.'}
                        ,{'8','.','.','.','6','.','.','.','3'}
                        ,{'4','.','.','8','.','3','.','.','1'}
                        ,{'7','.','.','.','2','.','.','.','6'}
                        ,{'.','6','.','.','.','.','2','8','.'}
                        ,{'.','.','.','4','1','9','.','.','5'}
                        ,{'.','.','.','.','8','.','.','7','9'}};

        System.out.println("数独是否有效："+isValidSudoku(board1));
        board1= new char[][] {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}
                            , {'6', '.', '.', '1', '9', '5', '.', '.', '.'}
                            , {'.', '9', '8', '.', '.', '.', '.', '6', '.'}
                            , {'8', '.', '.', '.', '6', '.', '.', '.', '3'}
                            , {'4', '.', '.', '8', '.', '3', '.', '.', '1'}
                            , {'7', '.', '.', '.', '2', '.', '.', '.', '6'}
                            , {'.', '6', '.', '.', '.', '.', '2', '8', '.'}
                            , {'.', '.', '.', '4', '1', '9', '.', '.', '5'}
                            , {'.', '.', '.', '.', '8', '.', '.', '2', '9'}};
        System.out.println("数独是否有效："+isValidSudoku(board1));
        board1=new char[][] {{'5','3','.','.','7','.','.','.','.'}
                            ,{'6','.','.','1','9','5','.','.','.'}
                            ,{'.','5','8','.','.','.','.','6','.'}
                            ,{'8','.','.','.','6','.','.','.','3'}
                            ,{'4','.','.','8','.','3','.','.','1'}
                            ,{'7','.','.','.','2','.','.','.','6'}
                            ,{'.','6','.','.','.','.','2','8','.'}
                            ,{'.','.','.','4','1','9','.','.','5'}
                            ,{'.','.','.','.','8','.','.','7','9'}};

        System.out.println("数独是否有效："+isValidSudoku(board1));
    }
/////////////////////////////////////////////////////////////////////////////////////////////////
    /**
     * 旋转矩阵 90°
     * 1.先上下交换
     * 2.斜对角交换
     * @param matrix
     */
    public void rotate(int[][] matrix){
        int length = matrix.length;
        int speed = length/2;
        int tmp = 0;
        // 上下换一半
        for (int i = 0; i < speed; i++) {
            tmp = length-i-1;
            for (int j = 0; j < length; j++) {
                matrix[i][j] = matrix[i][j]^matrix[tmp][j];
                matrix[tmp][j] = matrix[tmp][j]^matrix[i][j];
                matrix[i][j] = matrix[i][j]^matrix[tmp][j];
            }
        }
        // 对角线换一半
        for (int i = 0; i < length; i++) {
            for (int j = i+1; j < length; j++) {
                matrix[i][j] = matrix[i][j] ^ matrix[j][i];
                matrix[j][i] = matrix[i][j] ^ matrix[j][i];
                matrix[i][j] = matrix[i][j] ^ matrix[j][i];
            }
        }
    }

    void rotateTest(){
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        rotate(matrix);
        matrix = new int[][]{{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}};
        rotate(matrix);
    }

    /**
     * 给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
     *
     * 请注意，必须在不复制数组的情况下原地对数组进行操作。
     * @param nums
     */
    public void moveZeroes(int[] nums){
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                nums[index] = nums[i];
                index++;
            }
        }
        while (index<nums.length){
            nums[index]=0;
            index++;
        }
    }
    void moveZeroesTest(){
        int[] nums = new int[]{0,1,0,3,12};
        moveZeroes(nums);
        nums = new int[]{0};
        moveZeroes(nums);
        nums = new int[]{2};
        moveZeroes(nums);
        nums = new int[]{-1,-2,0,2};
        moveZeroes(nums);
        System.out.println();
    }

    /////////////////////////////////////////////////////////////////////

    /**
     *给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     *
     * 解法：逆序遍历、如果遇到9则+1 为0，如果没遇到则+1；如果遍历完没返回，则是全9，新数组首位为1
     * @param digits
     */
    public int[] plusOne(int[] digits){
        for (int i = digits.length-1; i > -1; i--) {
            if (digits[i]!=9){
                digits[i]++;
                return digits;
            }else{
                digits[i]=0;
            }
        }
        int[] ints = new int[digits.length+1];
        ints[0] = 1;
        return ints;
    }
    void plusOneTest(){
        int[] nums = {1,2,4,6};
        nums = plusOne(nums);
        nums = new int[]{9,9,9,9};
        nums = plusOne(nums);
        nums = new int[]{1,2,0,0};
        nums = plusOne(nums);
        System.out.println();
    }

    /////////////////////////////////////////////////////////////

    /**
     * 字符串反转
     * @param s
     * @return
     */
    public void reverseString(char[] s){
        int maxIndex = s.length-1;
        int index = s.length/2;
        for (int i = 0; i < index; i++) {
            s[i]^=s[maxIndex-i];
            s[maxIndex-i]^=s[i];
            s[i]^=s[maxIndex-i];
        }
    }
    void reverseStringTest(){
        char[] chars = null;
        reverseString(chars=new char[]{'a','b','c'});
        System.out.println();
        reverseString(chars=new char[]{'a','b','c','d'});
        System.out.println();
//        reverseString(new char[]{'a','b','c'});
    }

    /**
     * 给定一个字符串S，请你找出其中不含有重复字符的 最长子串 的长度
     */
    void maxSubString(String string){
        int j=0;
        Set<Character> tmp = new HashSet<>();
        Set<Character> result = new HashSet<>();
        int length = 0;
        
        char[] chars = string.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            for (int k = j; k < chars.length; k++) {
                if (tmp.contains(chars[k])){
                    result.removeAll(result);
                    result.addAll(tmp);
                    tmp.remove(chars[k]);
                    tmp.add(chars[k]);
                    j = k+1;
                    break;
                }else{
                    tmp.add(chars[k]);
                }
            }
            System.out.println(tmp);
        }
        System.out.println(tmp);
        System.out.println(tmp.size());

    }

    public static void main(String[] args) {
//        new Study().twoSumsTest();
//        new Study().addTwoNumbersTest();
//        new Study().isValidSudokuTest();
//        new Study().rotateTest();
//        new Study().moveZeroesTest();
//        new Study().plusOneTest();
//        new Study().reverseStringTest();
        new Study().maxSubString("abcabcbbd");
    }

}
